package cn.dapeng.tree.binary;

public class LowestAncestor {

    public static Info process(TreeNode x, TreeNode a, TreeNode b) {
        if (x == null) {
            return new Info(false, false, null);
        }
        Info leftTree = process(x.left, a, b);
        Info rightTree = process(x.right, a, b);

        boolean findA = (x == a) || leftTree.findA || rightTree.findA;
        boolean findB = (x == b) || rightTree.findB || rightTree.findB;

        TreeNode ans = null;
        if (leftTree.ans != null) {
            ans = leftTree.ans;
        } else if (rightTree.ans != null) {
            ans = rightTree.ans;
        } else {
            if (findA && findB) {
                ans = x;
            }
        }
        return new Info(findA, findB, ans);
    }

    static class Info {
        public boolean findA;
        public boolean findB;

        public TreeNode ans;

        public Info(boolean fA, boolean fB, TreeNode ans) {
            this.findA = fA;
            this.findB = fB;
            this.ans = ans;
        }
    }

}
